#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 10

typedef int ElemType;
typedef struct {
    ElemType *elem;
    int TableLen;
}SSTable;
//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
/**
 *          49 38 97 65
 *
 *     49  38            97  65     先分组
 * low      mid       mid+1   high
 *  49      38         97     65
 *
 *     38  49           65  97     再归并
 *
 *         38 49 65 97
 */
//合并两个有序数组
void Merge(ElemType *A,int low,int mid,int high)
{
    static ElemType B[N];   //用static的目的是五路递归多少次，都只有一个B[N]
    int i,j,k;
    for (i=0;i<=high;i++) { //把A[i]里的元素都给B[i]
        B[i]=A[i];
    }
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++) //合并两个有序数组
    {
        if(B[i]<B[j])
        {
            A[k]=B[i];  //B[i++]
            i++;
        } else{
            A[k]=B[j];
            j++;
        }
    }
    //把某一个数组剩余的元素放入
    while (i<=mid)
    {
        A[k]=B[i]; //前一半剩余的放入
        k++;
        i++;
    }
    while (j<=high)
    {
        A[k]=B[j]; //后一半剩余的放入
        k++;
        j++;
    }
}
//归并排序不限制是两两归并，还有多个归并，考研考的都是两两归并
void MergeSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        //先分组
        MergeSort(A,low,mid); //排序好前一半
        MergeSort(A,mid+1,high); //排序好后一半
        Merge(A,low,mid,high); //将两个排序好的数组合并
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,N);
    ElemType A[N]={3,87,2,93,78,56,61,38,12,40};
    //内存copy接口，当你copy整型数组，或者浮点型时，使用memcpy，不能用strcpy，初试考memcpy概率很低
    memcpy(ST.elem,A,sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    ST_Print(ST);
    MergeSort(ST.elem,0,N-1);
    ST_Print(ST);
    return 0;
}

